<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>Huffman树的编码与译码 | Cristor404</title><meta name="author" content="Cristor404"><meta name="copyright" content="Cristor404"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="构建一颗Huffman树已经对它进行译码编码">
<meta property="og:type" content="article">
<meta property="og:title" content="Huffman树的编码与译码">
<meta property="og:url" content="https://cristor404.gitee.io/2022/09/20/HuffmanTreeTest/index.html">
<meta property="og:site_name" content="Cristor404">
<meta property="og:description" content="构建一颗Huffman树已经对它进行译码编码">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://img-blog.csdnimg.cn/c2b374c28c4f4bab87091984fee27a2c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16">
<meta property="article:published_time" content="2022-09-20T08:09:00.000Z">
<meta property="article:modified_time" content="2022-09-20T08:53:47.710Z">
<meta property="article:author" content="Cristor404">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://img-blog.csdnimg.cn/c2b374c28c4f4bab87091984fee27a2c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://cristor404.gitee.io/2022/09/20/HuffmanTreeTest/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: undefined,
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: 'Huffman树的编码与译码',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2022-09-20 16:53:47'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><link rel="stylesheet" href="/css/mouse.css"><meta name="generator" content="Hexo 6.3.0"></head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://s2.loli.net/2022/09/19/8IjdtLPKe9b7vUg.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">8</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">0</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 访达</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友情链接</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://img-blog.csdnimg.cn/c2b374c28c4f4bab87091984fee27a2c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">Cristor404</a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 访达</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友情链接</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">Huffman树的编码与译码</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2022-09-20T08:09:00.000Z" title="发表于 2022-09-20 16:09:00">2022-09-20</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2022-09-20T08:53:47.710Z" title="更新于 2022-09-20 16:53:47">2022-09-20</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/">数据结构和算法</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="Huffman树的编码与译码"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="哈夫曼编码译码"><a href="#哈夫曼编码译码" class="headerlink" title="哈夫曼编码译码"></a>哈夫曼编码译码</h1><h2 id="先看题目："><a href="#先看题目：" class="headerlink" title="先看题目："></a>先看题目：</h2><p>首先这是一道PTA的题目，作为博主数据结构与算法这门课程的假期实践作业。</p>
<ul>
<li><p>编写一个哈夫曼编码译码程序:</p>
<p>  按词频从小到大的顺序给出各个字符（不超过30个）的词频，根据词频构造哈夫曼树，给出每个字符的哈夫曼编码，并对给出的语句进行译码。</p>
</li>
<li><p>为确保构建的哈夫曼树唯一，本题做如下限定：</p>
<p>  （1）选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。</p>
<p>  （2）若多棵二叉树根结点权值相等，按先后次序分左右，先出现的作为左子树，后出现的作为右子树。</p>
</li>
<li><p>生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。</p>
<p>  <strong>输入格式:</strong><br>  第一行输入字符个数n；</p>
<p>  第二行到第n行输入相应的字符及其词频(可以是整数，与可以是小数）；</p>
<p>  最后一行输入需进行译码的串。</p>
<p>  <strong>输出格式:</strong><br>  首先按树的先序顺序输出所有字符的编码，每个编码占一行；</p>
<p>  最后一行输出需译码的原文，加上original:字样。</p>
<p>  <em>输出中均无空格</em></p>
</li>
</ul>
<p><strong>输入样例:</strong></p>
<blockquote>
<p>3<br>m1<br>n1<br>c2<br>10110</p>
</blockquote>
<p><strong>输出样例:</strong></p>
<blockquote>
<p>c:0<br>m:10<br>n:11<br>original:mnc</p>
</blockquote>
<p><strong>题目分析：</strong></p>
<p>题目给出了n个字符以及他们的频率，也就是说给出了n个结点，让我们用这n个结点构建一个Huffman树，然后又给出一段哈夫曼编码，让我们在所构建的Huffman树的基础上，对该编码进行翻译。</p>
<p><em>所以这道题难点在于怎么构建这样一颗Huffman树(结点的选取、编码和译码)。</em></p>
<p><strong>实验步骤：</strong><br>根据Huffman树的性质我们可以知道，Huffman树中没有度为1得结点. <u>只有度为0和度为2得结点.</u> 则一棵 有n个叶子结点得哈夫曼树<u>共有2n-1个结点</u></p>
<p>所以题目给了n个结点(叶子结点)，那么我们构建的Huffman树就会有<u>2n-1个结点。</u></p>
<p><strong>不妨画图看看？</strong><br><img src="https://img-blog.csdnimg.cn/917371e7b96f430ca4632abb05c3c017.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" alt="Huffman树的结构"></p>
<p><strong>我们可以构建出这样一颗Huffman树，首先我们来创建一个树结点的结构体，每一个结点都存有:</strong><br><img src="https://img-blog.csdnimg.cn/9f409e22236f43aca672a918172ef4f7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" alt="单个结点"><br> 诶呀，图里忘记画 哈夫曼编码 这一项咯QWQ(也就是下图的char* code;)</p>
<p> <strong>↑对应的代码：</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//Huffman树结点结构体</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> <span class="title class_">TreeNode</span>&#123;</span><br><span class="line">	<span class="type">double</span> weight;<span class="comment">//因为频率有可能为小数，所以用double</span></span><br><span class="line">	<span class="type">char</span> Ch;<span class="comment">//用于存放该节点字符</span></span><br><span class="line">	<span class="type">char</span> *code;<span class="comment">//用于存放该字符的 Huffman编码</span></span><br><span class="line">	<span class="type">int</span> parent,lchild,rchild;<span class="comment">//存放每个结点的 父节点 以及 子结点</span></span><br><span class="line">&#125;TreeNode;</span><br></pre></td></tr></table></figure>
<p><strong>然后，将这些结点组合起来，形成一颗树：</strong><br><img src="https://img-blog.csdnimg.cn/a82e6aa8322f4837a361ceaf5b5f7a38.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" alt="一堆结点结合形成树"><br> <strong>↑对应的代码：</strong><br> <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"> <span class="comment">//Huffman树结构体</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> <span class="title class_">HFTree</span>&#123;</span><br><span class="line">	TreeNode* data;<span class="comment">//用堆实现该Huffman树</span></span><br><span class="line">	<span class="type">int</span> length;<span class="comment">//该树总结点的个数</span></span><br><span class="line">&#125;HFTree;</span><br></pre></td></tr></table></figure><br><strong>好的，构建完树的结构体之后呢，我们可以先编写程序的输入(main)部分：</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX_INT 1000</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX_Double (numeric_limits<span class="string">&lt;double&gt;</span>::max)()</span></span><br><span class="line"> </span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="comment">//输入n个字符</span></span><br><span class="line">	<span class="type">int</span> n;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">	<span class="built_in">getchar</span>();<span class="comment">//吸收缓存中的回车符，以下同理</span></span><br><span class="line">	</span><br><span class="line">	<span class="comment">//初始化n个 char和double类型的数组 用于存放 字符和对应的频率</span></span><br><span class="line">	<span class="type">char</span>* chNums = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">char</span>)*n);</span><br><span class="line">	<span class="type">double</span>* nuNums = (<span class="type">double</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">double</span>)*n);</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//输入 字符以及相应的频率</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;n;++i)&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%c%lf&quot;</span>,&amp;chNums[i],&amp;nuNums[i]);</span><br><span class="line">		<span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//输入 需要译码的字符串</span></span><br><span class="line">	<span class="type">char</span> str[MAX_INT];</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,str);</span><br><span class="line">	<span class="built_in">getchar</span>();</span><br><span class="line"> </span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>好的，这样我们就拿到的输入的数据，接下来我们需要对拿到的字符和频率（也就是结点）进行Huffman树的构造咯！</strong></p>
<p>我们可以写一个初始化函数：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//初始化哈夫曼树</span></span><br><span class="line"><span class="comment">//把输入的 字符 频率 字符个数 传进来</span></span><br><span class="line"><span class="function">HFTree* <span class="title">initTree</span><span class="params">(<span class="type">double</span>* weight,<span class="type">char</span>* ch,<span class="type">int</span> n)</span></span>&#123;</span><br><span class="line">	HFTree* T = (HFTree*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(HFTree));</span><br><span class="line">	<span class="comment">//根据性质，n个结点生成的Huffman树会有2*n-1个结点</span></span><br><span class="line">	T-&gt;data = (TreeNode*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(TreeNode)*(<span class="number">2</span>*n<span class="number">-1</span>));</span><br><span class="line">	T-&gt;length = n;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//初始化每个结点，我们先给这n个结点(叶子结点)先初始化，等一下再初始化后面的n-1个(父结点)</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; ++i)&#123;</span><br><span class="line">        <span class="comment">//给结点中的每一个数据项赋值</span></span><br><span class="line">		T-&gt;data[i].Ch = ch[i];</span><br><span class="line">		T-&gt;data[i].weight = weight[i];</span><br><span class="line">        </span><br><span class="line">        <span class="comment">//没有父节点就默认为0</span></span><br><span class="line">		T-&gt;data[i].parent = <span class="number">0</span>;</span><br><span class="line"> </span><br><span class="line">        <span class="comment">//没有孩子结点就默认为-1</span></span><br><span class="line">		T-&gt;data[i].lchild = <span class="number">-1</span>;</span><br><span class="line">		T-&gt;data[i].rchild = <span class="number">-1</span>;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//初始化每个结点的code数组</span></span><br><span class="line">		T-&gt;data[i].code = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">char</span>)*MAX_INT);</span><br><span class="line">		<span class="built_in">memset</span>(T-&gt;data[i].code,<span class="string">&#x27;\0&#x27;</span>,MAX_INT);	</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> T;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>初始化之后呢，树的状态就为下图所示咯：(只初始化给定的结点，之后的结点我们后续构造)<br><img src="https://img-blog.csdnimg.cn/fee665e3d47d40cc899953790194592d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" alt="初始化输入的结点"></p>
<p><strong>下面就是创建一个Huffmna树的函数咯，但是我们还需要做一些准备：</strong><br>因为在创建一颗Huffman树时，需要从所有结点之中，选择两个权值最小的结点来进行组合，所以我们需要先编写一个<strong>选择最小两个结点的下标的函数：</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//选择两个权值最小的结点,每次都会返回两个最小的结点</span></span><br><span class="line"><span class="function"><span class="type">int</span>* <span class="title">selectMin</span><span class="params">(HFTree* T)</span></span>&#123;</span><br><span class="line">	<span class="comment">//定义两个哨兵变量，他们的值为double所表示的最大值</span></span><br><span class="line">	<span class="comment">//(numeric_limits&lt;double&gt;::max)();</span></span><br><span class="line">	<span class="type">double</span> min = MAX_Double;</span><br><span class="line">	<span class="type">double</span> secondMin = MAX_Double;</span><br><span class="line">	<span class="comment">//两个最小结点的下标</span></span><br><span class="line">	<span class="type">int</span> minIndex;</span><br><span class="line">	<span class="type">int</span> secondIndex;</span><br><span class="line">	<span class="comment">//先选择第一小的结点</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;T-&gt;length;++i)&#123;</span><br><span class="line">		<span class="comment">//只要没有父节点就可以选择</span></span><br><span class="line">		<span class="keyword">if</span>(T-&gt;data[i].parent == <span class="number">0</span>)&#123;</span><br><span class="line">			<span class="keyword">if</span>(T-&gt;data[i].weight &lt; min)&#123;</span><br><span class="line">				min = T-&gt;data[i].weight;</span><br><span class="line">				minIndex = i;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//其次选择第二小的结点</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i =<span class="number">0</span>;i&lt;T-&gt;length;++i)&#123;</span><br><span class="line">		<span class="comment">//没有父节点且不等于第一小的才选择</span></span><br><span class="line">		<span class="keyword">if</span>(T-&gt;data[i].parent == <span class="number">0</span> &amp;&amp; i != minIndex)&#123;</span><br><span class="line">			<span class="keyword">if</span>(T-&gt;data[i].weight &lt; secondMin)&#123;</span><br><span class="line">				secondMin = T-&gt;data[i].weight;</span><br><span class="line">				secondIndex = i;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//因为返回两个值，所以可以使用指针</span></span><br><span class="line">	<span class="type">int</span>* res = (<span class="type">int</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">int</span>)*<span class="number">2</span>);</span><br><span class="line">	res[<span class="number">0</span>] = minIndex;</span><br><span class="line">	res[<span class="number">1</span>] = secondIndex;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>有了这玩意之后，我们就可以很开心的来写一个构建Huffmna树的函数咯！(把给定的叶子结点进行结合，从下往上构建父结点)</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//创建Huffman树</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">createHFTree</span><span class="params">(HFTree* T,<span class="type">int</span> nn)</span></span>&#123;</span><br><span class="line">	<span class="type">int</span>* res;    <span class="comment">//用于接收选择的两个最小结点</span></span><br><span class="line">	<span class="type">int</span> min;     <span class="comment">//第一小结点的下标</span></span><br><span class="line">	<span class="type">int</span> secondMin;    <span class="comment">//第二小结点的下标</span></span><br><span class="line">	<span class="type">int</span> n = T-&gt;length * <span class="number">2</span> - <span class="number">1</span>;</span><br><span class="line"> </span><br><span class="line">    <span class="comment">//从下标n开始往后构建父子结点</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = T-&gt;length; i &lt; n;++i)&#123;</span><br><span class="line">		T-&gt;data[i].parent = <span class="number">0</span>;</span><br><span class="line">		res = <span class="built_in">selectMin</span>(T);<span class="comment">//选择两个最小的结点</span></span><br><span class="line">		min = res[<span class="number">0</span>];</span><br><span class="line">		secondMin = res[<span class="number">1</span>];</span><br><span class="line"> </span><br><span class="line">		<span class="comment">//给父节点赋值</span></span><br><span class="line">		T-&gt;data[i].weight = T-&gt;data[min].weight + T-&gt;data[secondMin].weight;</span><br><span class="line">		T-&gt;data[i].lchild = min;</span><br><span class="line">		T-&gt;data[i].rchild = secondMin;</span><br><span class="line"> </span><br><span class="line">		<span class="comment">//给儿子们赋值</span></span><br><span class="line">		T-&gt;data[min].parent = i;</span><br><span class="line">		T-&gt;data[secondMin].parent = i;</span><br><span class="line">		T-&gt;length++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//为每个字符编码</span></span><br><span class="line">	<span class="built_in">Hfmcode</span>(T,nn);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>这是结合完毕之后的树结构状态图：</strong><br><img src="https://img-blog.csdnimg.cn/c2b374c28c4f4bab87091984fee27a2c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" alt="创建树后"><br>发现变化了嘛?<br>那么这个树的结构算是给我们给整出来了，但是每一个结点都还差自己的一个东西，那就是他们的Huffman编码！<br>根据题意：哈夫曼树左分支标记为0，右分支标记为1，那么3个叶子结点的Huffman编码就如下：<br><img src="https://img-blog.csdnimg.cn/56989fcad3344e25b821b8f3645ad79b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" alt="叶子节点的Huffmna编码"><br><strong>开始编写编码器：</strong></p>
<blockquote>
<p>基本思路：<br><BR>我们可以从叶子节点开始回溯，创建一个字符串用来存Huffman编码，左孩子就接‘0’ 右孩子就接‘1’  直到回溯到的结点的父亲为0时停止，拿m来举例：<br><BR>最后得到的字符串为：01 这与我们的预期相反 所以我们要逆序将这个字符串加入到结点的哈夫曼编码项中，此时m这个叶子结点的code项就为：10 符合我们的预期！</p>
</blockquote>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//Huffman编码器</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Hfmcode</span><span class="params">(HFTree* T,<span class="type">int</span> n)</span></span>&#123;</span><br><span class="line">	<span class="comment">//分别给n个字符编码</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>;k&lt;n;k++)&#123;</span><br><span class="line">	<span class="comment">//从0号位的叶子节点开始回溯</span></span><br><span class="line">	    <span class="type">int</span> i = <span class="number">0</span>,j = <span class="number">0</span>;</span><br><span class="line">	    <span class="type">int</span> ch = k;</span><br><span class="line">	    <span class="comment">//记录单个字符的编码</span></span><br><span class="line">	    <span class="type">char</span> str[MAX_INT];</span><br><span class="line">	    <span class="built_in">memset</span>(str,<span class="string">&#x27;\0&#x27;</span>,MAX_INT);</span><br><span class="line">		<span class="type">int</span> parent = T-&gt;data[k].parent;</span><br><span class="line">			<span class="keyword">for</span>(i = n<span class="number">-1</span>;parent != <span class="number">0</span>;i--)&#123;</span><br><span class="line">			<span class="comment">//如果该左孩子与 回溯起点index相符</span></span><br><span class="line">				<span class="keyword">if</span>(T-&gt;data[parent].lchild == ch)&#123;</span><br><span class="line">					str[j++] = <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">					ch = parent;</span><br><span class="line">					<span class="comment">//向上回溯</span></span><br><span class="line">					parent = T-&gt;data[ch].parent;</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					<span class="comment">//同上 右孩子.....</span></span><br><span class="line">					str[j++] = <span class="string">&#x27;1&#x27;</span>;</span><br><span class="line">					ch = parent;</span><br><span class="line">					parent = T-&gt;data[ch].parent;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		<span class="type">int</span> f = <span class="number">0</span>;</span><br><span class="line">		<span class="comment">//因为是回溯编码，所以需要反转存入结点中</span></span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> s = j<span class="number">-1</span>;s&gt;=<span class="number">0</span>;s--)&#123;</span><br><span class="line">			T-&gt;data[k].code[f] = str[s];</span><br><span class="line">			f++;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这时，我们的Huffman树就算是正式构建完毕，所有的结点都有了参数咯，那么我们不妨将它遍历出来看看！</p>
<p><strong>来写一个遍历函数吧：</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//递归遍历Huffman树 T-&gt;length-1为根结点</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">preOrder</span><span class="params">(HFTree* T,<span class="type">int</span> index)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(index != <span class="number">-1</span>)&#123;</span><br><span class="line">        <span class="comment">//只遍历叶子结点</span></span><br><span class="line">		<span class="keyword">if</span>(T-&gt;data[index].lchild == <span class="number">-1</span> || T-&gt;data[index].rchild == <span class="number">-1</span>)</span><br><span class="line">			cout &lt;&lt; T-&gt;data[index].Ch &lt;&lt;<span class="string">&quot;:&quot;</span>&lt;&lt;T-&gt;data[index].code&lt;&lt;endl;</span><br><span class="line">		<span class="built_in">preOrder</span>(T,T-&gt;data[index].lchild);</span><br><span class="line">		<span class="built_in">preOrder</span>(T,T-&gt;data[index].rchild);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>我们得到了这样的结果：</p>
<p><img src="https://img-blog.csdnimg.cn/ebc5138569c94c0a88ffe16370e4fe59.png" alt="第一次遍历的结果"></p>
<p> <strong>嗯嗯，很好，接下来最后一件事情就是给题目给出的这一段谜语来个翻译就欧克！</strong></p>
<p> <strong>再来一个解码函数：</strong><br> <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"> <span class="comment">//Huffman译码</span></span><br><span class="line"><span class="function"><span class="type">char</span>* <span class="title">Decode</span><span class="params">(<span class="type">char</span>* str,<span class="type">int</span> length,HFTree* T)</span></span>&#123;</span><br><span class="line">	<span class="type">int</span> index = length - <span class="number">1</span>,ct = <span class="number">0</span>,j = <span class="number">0</span>;</span><br><span class="line">	<span class="type">char</span> ch;</span><br><span class="line">	ch = str[<span class="number">0</span>];</span><br><span class="line">	<span class="type">char</span>* res = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">char</span>)*MAX_INT);</span><br><span class="line">	<span class="keyword">while</span>(<span class="literal">true</span>)&#123;</span><br><span class="line">		<span class="comment">//当密文字符为0时向左走</span></span><br><span class="line">		<span class="keyword">if</span>(ch == <span class="string">&#x27;0&#x27;</span>)&#123;</span><br><span class="line">			index = T-&gt;data[index].lchild;</span><br><span class="line">			<span class="comment">//为1时向右走</span></span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(ch == <span class="string">&#x27;1&#x27;</span>)&#123;</span><br><span class="line">			index = T-&gt;data[index].rchild;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//直到遍历到叶子节点</span></span><br><span class="line">		<span class="keyword">if</span>(T-&gt;data[index].lchild == <span class="number">-1</span> || T-&gt;data[index].rchild == <span class="number">-1</span>)&#123;</span><br><span class="line">			<span class="comment">//此时的字符值即为这一段密文的密码字符</span></span><br><span class="line">			res[ct] = T-&gt;data[index].Ch;</span><br><span class="line">			ct++;</span><br><span class="line">			<span class="comment">//回到根结点</span></span><br><span class="line">			index = length<span class="number">-1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//记录当前遍历密文的位置</span></span><br><span class="line">		j++;</span><br><span class="line">		ch = str[j];</span><br><span class="line">		<span class="comment">//当走完时直接及解码完成 退出循环</span></span><br><span class="line">		<span class="keyword">if</span>(j == (<span class="type">int</span>)<span class="built_in">strlen</span>(str))</span><br><span class="line">			<span class="keyword">break</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br> ok大功告成，我们来看看结果吧！</p>
<p> <img src="https://img-blog.csdnimg.cn/f749a630d5c345f79ca5f6699a1fd2d0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_11,color_FFFFFF,t_70,g_se,x_16" alt="第二次输出结果"></p>
<p> 上PTA看看结果捏:<br> <img src="https://img-blog.csdnimg.cn/168d25721ae6480faa04c9f49ec1353b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" alt="测试结果"></p>
<p> 完整代码:<br> <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br></pre></td><td class="code"><pre><span class="line"> <span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX_INT 1000</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX_Double (numeric_limits<span class="string">&lt;double&gt;</span>::max)()</span></span><br><span class="line"> </span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"> </span><br><span class="line"><span class="comment">//Huffman树结点结构体</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> <span class="title class_">TreeNode</span>&#123;</span><br><span class="line">	<span class="type">double</span> weight;<span class="comment">//因为频率有可能为小数，所以用double</span></span><br><span class="line">	<span class="type">char</span> Ch;<span class="comment">//用于存放该节点字符</span></span><br><span class="line">	<span class="type">char</span> *code;<span class="comment">//用于存放该字符的 Huffman编码</span></span><br><span class="line">	<span class="type">int</span> parent,lchild,rchild;<span class="comment">//存放每个结点的 父节点 以及 子结点</span></span><br><span class="line">&#125;TreeNode;</span><br><span class="line"> </span><br><span class="line"><span class="comment">//Huffman树结构体</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> <span class="title class_">HFTree</span>&#123;</span><br><span class="line">	TreeNode* data;<span class="comment">//用堆实现该Huffman树</span></span><br><span class="line">	<span class="type">int</span> length;<span class="comment">//该树总结点的个数</span></span><br><span class="line">&#125;HFTree;</span><br><span class="line"> </span><br><span class="line"><span class="comment">//初始化哈夫曼树</span></span><br><span class="line"><span class="function">HFTree* <span class="title">initTree</span><span class="params">(<span class="type">double</span>* weight,<span class="type">char</span>* ch,<span class="type">int</span> n)</span></span>&#123;</span><br><span class="line">	HFTree* T = (HFTree*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(HFTree));</span><br><span class="line">	<span class="comment">//根据性质，n个结点生成的Huffman树会有2*n-1个结点</span></span><br><span class="line">	T-&gt;data = (TreeNode*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(TreeNode)*(<span class="number">2</span>*n<span class="number">-1</span>));</span><br><span class="line">	T-&gt;length = n;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//初始化每个结点</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; ++i)&#123;</span><br><span class="line">		T-&gt;data[i].Ch = ch[i];</span><br><span class="line">		T-&gt;data[i].weight = weight[i];</span><br><span class="line">		T-&gt;data[i].parent = <span class="number">0</span>;</span><br><span class="line">		T-&gt;data[i].lchild = <span class="number">-1</span>;</span><br><span class="line">		T-&gt;data[i].rchild = <span class="number">-1</span>;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//初始化每个结点的code数组</span></span><br><span class="line">		T-&gt;data[i].code = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">char</span>)*MAX_INT);</span><br><span class="line">		<span class="built_in">memset</span>(T-&gt;data[i].code,<span class="string">&#x27;\0&#x27;</span>,MAX_INT);	</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> T;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="comment">//选择两个权值最小的结点</span></span><br><span class="line"><span class="function"><span class="type">int</span>* <span class="title">selectMin</span><span class="params">(HFTree* T)</span></span>&#123;</span><br><span class="line">	<span class="comment">//定义两个哨兵变量，他们的值为double所表示的最大值</span></span><br><span class="line">	<span class="comment">//(numeric_limits&lt;double&gt;::max)();</span></span><br><span class="line">	<span class="type">double</span> min = MAX_Double;</span><br><span class="line">	<span class="type">double</span> secondMin = MAX_Double;</span><br><span class="line">	<span class="comment">//两个最小结点的下标</span></span><br><span class="line">	<span class="type">int</span> minIndex;</span><br><span class="line">	<span class="type">int</span> secondIndex;</span><br><span class="line">	<span class="comment">//先选择第一小的结点</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;T-&gt;length;++i)&#123;</span><br><span class="line">		<span class="comment">//只要没有父节点就可以选择</span></span><br><span class="line">		<span class="keyword">if</span>(T-&gt;data[i].parent == <span class="number">0</span>)&#123;</span><br><span class="line">			<span class="keyword">if</span>(T-&gt;data[i].weight &lt; min)&#123;</span><br><span class="line">				min = T-&gt;data[i].weight;</span><br><span class="line">				minIndex = i;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//其次选择第二小的结点</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i =<span class="number">0</span>;i&lt;T-&gt;length;++i)&#123;</span><br><span class="line">		<span class="comment">//没有父节点且不等于第一小的才选择</span></span><br><span class="line">		<span class="keyword">if</span>(T-&gt;data[i].parent == <span class="number">0</span> &amp;&amp; i != minIndex)&#123;</span><br><span class="line">			<span class="keyword">if</span>(T-&gt;data[i].weight &lt; secondMin)&#123;</span><br><span class="line">				secondMin = T-&gt;data[i].weight;</span><br><span class="line">				secondIndex = i;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//因为返回两个值，所以可以使用指针</span></span><br><span class="line">	<span class="type">int</span>* res = (<span class="type">int</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">int</span>)*<span class="number">2</span>);</span><br><span class="line">	res[<span class="number">0</span>] = minIndex;</span><br><span class="line">	res[<span class="number">1</span>] = secondIndex;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="comment">//Huffman编码器</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Hfmcode</span><span class="params">(HFTree* T,<span class="type">int</span> n)</span></span>&#123;</span><br><span class="line">	<span class="comment">//分别给n个字符编码</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>;k&lt;n;k++)&#123;</span><br><span class="line">	<span class="comment">//从0号位的叶子节点开始回溯</span></span><br><span class="line">	    <span class="type">int</span> i = <span class="number">0</span>,j = <span class="number">0</span>;</span><br><span class="line">	    <span class="type">int</span> ch = k;</span><br><span class="line">	    <span class="comment">//记录单个字符的编码</span></span><br><span class="line">	    <span class="type">char</span> str[MAX_INT];</span><br><span class="line">	    <span class="built_in">memset</span>(str,<span class="string">&#x27;\0&#x27;</span>,MAX_INT);</span><br><span class="line">		<span class="type">int</span> parent = T-&gt;data[k].parent;</span><br><span class="line">			<span class="keyword">for</span>(i = n<span class="number">-1</span>;parent != <span class="number">0</span>;i--)&#123;</span><br><span class="line">			<span class="comment">//如果该左孩子与 回溯起点index相符</span></span><br><span class="line">				<span class="keyword">if</span>(T-&gt;data[parent].lchild == ch)&#123;</span><br><span class="line">					str[j++] = <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">					ch = parent;</span><br><span class="line">					<span class="comment">//向上回溯</span></span><br><span class="line">					parent = T-&gt;data[ch].parent;</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					<span class="comment">//同上 右孩子.....</span></span><br><span class="line">					str[j++] = <span class="string">&#x27;1&#x27;</span>;</span><br><span class="line">					ch = parent;</span><br><span class="line">					parent = T-&gt;data[ch].parent;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		<span class="type">int</span> f = <span class="number">0</span>;</span><br><span class="line">		<span class="comment">//因为是回溯编码，所以需要反转</span></span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> s = j<span class="number">-1</span>;s&gt;=<span class="number">0</span>;s--)&#123;</span><br><span class="line">			T-&gt;data[k].code[f] = str[s];</span><br><span class="line">			f++;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="comment">//创建Huffman树</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">createHFTree</span><span class="params">(HFTree* T,<span class="type">int</span> nn)</span></span>&#123;</span><br><span class="line">	<span class="type">int</span>* res;</span><br><span class="line">	<span class="type">int</span> min;</span><br><span class="line">	<span class="type">int</span> secondMin;</span><br><span class="line">	<span class="type">int</span> n = T-&gt;length * <span class="number">2</span> - <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = T-&gt;length; i &lt; n;++i)&#123;</span><br><span class="line">		T-&gt;data[i].parent = <span class="number">0</span>;</span><br><span class="line">		res = <span class="built_in">selectMin</span>(T);</span><br><span class="line">		min = res[<span class="number">0</span>];</span><br><span class="line">		secondMin = res[<span class="number">1</span>];</span><br><span class="line">		<span class="comment">//给父节点赋值</span></span><br><span class="line">		T-&gt;data[i].weight = T-&gt;data[min].weight + T-&gt;data[secondMin].weight;</span><br><span class="line">		T-&gt;data[i].lchild = min;</span><br><span class="line">		T-&gt;data[i].rchild = secondMin;</span><br><span class="line">		<span class="comment">//给儿子们赋值</span></span><br><span class="line">		T-&gt;data[min].parent = i;</span><br><span class="line">		T-&gt;data[secondMin].parent = i;</span><br><span class="line">		T-&gt;length++;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//为每个字符编码</span></span><br><span class="line">	<span class="built_in">Hfmcode</span>(T,nn);</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="comment">//递归遍历Huffman树 T-&gt;length-1为根结点</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">preOrder</span><span class="params">(HFTree* T,<span class="type">int</span> index)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(index != <span class="number">-1</span>)&#123;</span><br><span class="line">		<span class="keyword">if</span>(T-&gt;data[index].lchild == <span class="number">-1</span> || T-&gt;data[index].rchild == <span class="number">-1</span>)</span><br><span class="line">			cout &lt;&lt; T-&gt;data[index].Ch &lt;&lt;<span class="string">&quot;:&quot;</span>&lt;&lt;T-&gt;data[index].code&lt;&lt;endl;</span><br><span class="line">		<span class="built_in">preOrder</span>(T,T-&gt;data[index].lchild);</span><br><span class="line">		<span class="built_in">preOrder</span>(T,T-&gt;data[index].rchild);</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="comment">//Huffman译码</span></span><br><span class="line"><span class="function"><span class="type">char</span>* <span class="title">Decode</span><span class="params">(<span class="type">char</span>* str,<span class="type">int</span> length,HFTree* T)</span></span>&#123;</span><br><span class="line">	<span class="type">int</span> index = length - <span class="number">1</span>,ct = <span class="number">0</span>,j = <span class="number">0</span>;</span><br><span class="line">	<span class="type">char</span> ch;</span><br><span class="line">	ch = str[<span class="number">0</span>];</span><br><span class="line">	<span class="type">char</span>* res = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">char</span>)*MAX_INT);</span><br><span class="line">	<span class="keyword">while</span>(<span class="literal">true</span>)&#123;</span><br><span class="line">		<span class="comment">//当密文字符为0时向左走</span></span><br><span class="line">		<span class="keyword">if</span>(ch == <span class="string">&#x27;0&#x27;</span>)&#123;</span><br><span class="line">			index = T-&gt;data[index].lchild;</span><br><span class="line">			<span class="comment">//为1时向右走</span></span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(ch == <span class="string">&#x27;1&#x27;</span>)&#123;</span><br><span class="line">			index = T-&gt;data[index].rchild;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//直到遍历到叶子节点</span></span><br><span class="line">		<span class="keyword">if</span>(T-&gt;data[index].lchild == <span class="number">-1</span> || T-&gt;data[index].rchild == <span class="number">-1</span>)&#123;</span><br><span class="line">			<span class="comment">//此时的字符值即为这一段密文的密码字符</span></span><br><span class="line">			res[ct] = T-&gt;data[index].Ch;</span><br><span class="line">			ct++;</span><br><span class="line">			<span class="comment">//回到根结点</span></span><br><span class="line">			index = length<span class="number">-1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//记录当前遍历密文的位置</span></span><br><span class="line">		j++;</span><br><span class="line">		ch = str[j];</span><br><span class="line">		<span class="comment">//当走完时直接及解码完成 退出循环</span></span><br><span class="line">		<span class="keyword">if</span>(j == (<span class="type">int</span>)<span class="built_in">strlen</span>(str))</span><br><span class="line">			<span class="keyword">break</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="comment">//输入n个字符</span></span><br><span class="line">	<span class="type">int</span> n;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">	<span class="built_in">getchar</span>();</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//初始化n个 char和double类型的数组 用于存放 字符和对应的频率</span></span><br><span class="line">	<span class="type">char</span>* chNums = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">char</span>)*n);</span><br><span class="line">	<span class="type">double</span>* nuNums = (<span class="type">double</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">double</span>)*n);</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//输入 字符以及相应的频率</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;n;++i)&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%c%lf&quot;</span>,&amp;chNums[i],&amp;nuNums[i]);</span><br><span class="line">		<span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//输入 需要译码的字符串</span></span><br><span class="line">	<span class="type">char</span> str[MAX_INT];</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,str);</span><br><span class="line">	<span class="built_in">getchar</span>();</span><br><span class="line">	<span class="comment">//创建一棵Huffman树</span></span><br><span class="line">	HFTree* T = <span class="built_in">initTree</span>(nuNums,chNums,n);</span><br><span class="line">	<span class="built_in">createHFTree</span>(T,n);</span><br><span class="line">	<span class="comment">//遍历每个字符及其编码</span></span><br><span class="line">	<span class="built_in">preOrder</span>(T,T-&gt;length<span class="number">-1</span>);</span><br><span class="line">	<span class="comment">//遍历解码后的密文</span></span><br><span class="line">	cout&lt;&lt;<span class="string">&quot;original:&quot;</span>&lt;&lt;<span class="built_in">Decode</span>(str,T-&gt;length,T)&lt;&lt;endl;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<blockquote>
<p>博主的编程水平比较菜，写这一题花了挺长时间的，主要卡在了给每个字符编码，但是在写完了编码函数提交之后，第一个测试点不通过，以为是自己的思路有问题，而且PTA也不给测试点的数据，搞得不知道哪里出问题了，改了好几天，最后发现，原来是在判断最小的两个结点时，哨兵的值设置的太小，然后测试点给了一个很大的频率，导致一直没过，也是随便改改提交突然全过了，算是乱碰给碰出来了hhh，发出来给大家借鉴一下，如果你有更好的想法的画，欢迎与博主进行讨论交流！</p>
</blockquote>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="https://cristor404.gitee.io">Cristor404</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://cristor404.gitee.io/2022/09/20/HuffmanTreeTest/">https://cristor404.gitee.io/2022/09/20/HuffmanTreeTest/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://cristor404.gitee.io" target="_blank">Cristor404</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"></div><div class="post_share"><div class="social-share" data-image="https://img-blog.csdnimg.cn/c2b374c28c4f4bab87091984fee27a2c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2022/09/20/Crsitor%E7%9A%84%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/"><img class="prev-cover" src="https://gimg2.baidu.com/image_search/src=http%3A%2F%2Fimage1.big-bit.com%2F2021%2F0510%2F20210510024124509.jpeg&amp;refer=http%3A%2F%2Fimage1.big-bit.com&amp;app=2002&amp;size=f9999,10000&amp;q=a80&amp;n=0&amp;g=0n&amp;fmt=auto?sec=1672154822&amp;t=49b9b7598a8c874b43bcce547cc000a3" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">Cristor计算机系统的笔记</div></div></a></div><div class="next-post pull-right"><a href="/2022/09/20/%E5%AE%B9%E5%99%A8%E5%8C%96%E4%B8%80%E4%B8%AAJava%E5%BA%94%E7%94%A8%E7%A8%8B%E5%BA%8F/"><img class="next-cover" src="https://img1.baidu.com/it/u=4236520888,410323430&amp;fm=253&amp;fmt=auto&amp;app=138&amp;f=JPG?w=918&amp;h=500" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">容器化Java应用程序</div></div></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://s2.loli.net/2022/09/19/8IjdtLPKe9b7vUg.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">Cristor404</div><div class="author-info__description">分享一些个人学习的心得</div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">8</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">0</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/Cristor404"><i class="fab fa-github"></i><span>关 注 我</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/Cristor404" target="_blank" title=""><i class="fab fa-github"></i></a><a class="social-icon" href="mailto:2412215074@qq.com" target="_blank" title=""><i class="fas fa-envelope"></i></a><a class="social-icon" href="https://music.163.com/#/artist?id=1158066" target="_blank" title=""><i class="fa-solid fa-music"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">会不定期的更新一些文章哦</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81%E8%AF%91%E7%A0%81"><span class="toc-number">1.</span> <span class="toc-text">哈夫曼编码译码</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%85%88%E7%9C%8B%E9%A2%98%E7%9B%AE%EF%BC%9A"><span class="toc-number">1.1.</span> <span class="toc-text">先看题目：</span></a></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2023/01/03/%E5%9F%BA%E6%9C%AC%E5%88%9D%E7%AD%89%E5%87%BD%E6%95%B0/" title="无题"><img src="https://s2.loli.net/2022/09/19/pSDUbnYN2LJ61Is.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="无题"/></a><div class="content"><a class="title" href="/2023/01/03/%E5%9F%BA%E6%9C%AC%E5%88%9D%E7%AD%89%E5%87%BD%E6%95%B0/" title="无题">无题</a><time datetime="2023-01-03T13:08:00.357Z" title="发表于 2023-01-03 21:08:00">2023-01-03</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/11/27/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/" title="排序算法"><img src="http://mms0.baidu.com/it/u=1186296230,3449077382&amp;fm=253&amp;app=138&amp;f=PNG&amp;fmt=auto&amp;q=75?w=634&amp;h=291" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="排序算法"/></a><div class="content"><a class="title" href="/2022/11/27/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/" title="排序算法">排序算法</a><time datetime="2022-11-27T11:30:00.000Z" title="发表于 2022-11-27 19:30:00">2022-11-27</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/09/20/Crsitor%E7%9A%84%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/" title="Cristor计算机系统的笔记"><img src="https://gimg2.baidu.com/image_search/src=http%3A%2F%2Fimage1.big-bit.com%2F2021%2F0510%2F20210510024124509.jpeg&amp;refer=http%3A%2F%2Fimage1.big-bit.com&amp;app=2002&amp;size=f9999,10000&amp;q=a80&amp;n=0&amp;g=0n&amp;fmt=auto?sec=1672154822&amp;t=49b9b7598a8c874b43bcce547cc000a3" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Cristor计算机系统的笔记"/></a><div class="content"><a class="title" href="/2022/09/20/Crsitor%E7%9A%84%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/" title="Cristor计算机系统的笔记">Cristor计算机系统的笔记</a><time datetime="2022-09-20T12:30:00.000Z" title="发表于 2022-09-20 20:30:00">2022-09-20</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/09/20/HuffmanTreeTest/" title="Huffman树的编码与译码"><img src="https://img-blog.csdnimg.cn/c2b374c28c4f4bab87091984fee27a2c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQ3Jpc3RvcjQwNA==,size_20,color_FFFFFF,t_70,g_se,x_16" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Huffman树的编码与译码"/></a><div class="content"><a class="title" href="/2022/09/20/HuffmanTreeTest/" title="Huffman树的编码与译码">Huffman树的编码与译码</a><time datetime="2022-09-20T08:09:00.000Z" title="发表于 2022-09-20 16:09:00">2022-09-20</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/09/20/%E5%AE%B9%E5%99%A8%E5%8C%96%E4%B8%80%E4%B8%AAJava%E5%BA%94%E7%94%A8%E7%A8%8B%E5%BA%8F/" title="容器化Java应用程序"><img src="https://img1.baidu.com/it/u=4236520888,410323430&amp;fm=253&amp;fmt=auto&amp;app=138&amp;f=JPG?w=918&amp;h=500" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="容器化Java应用程序"/></a><div class="content"><a class="title" href="/2022/09/20/%E5%AE%B9%E5%99%A8%E5%8C%96%E4%B8%80%E4%B8%AAJava%E5%BA%94%E7%94%A8%E7%A8%8B%E5%BA%8F/" title="容器化Java应用程序">容器化Java应用程序</a><time datetime="2022-09-20T08:09:00.000Z" title="发表于 2022-09-20 16:09:00">2022-09-20</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2022 - 2023 By Cristor404</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.umd.min.js"></script><div class="js-pjax"><script>if (!window.MathJax) {
  window.MathJax = {
    tex: {
      inlineMath: [ ['$','$'], ["\\(","\\)"]],
      tags: 'ams'
    },
    chtml: {
      scale: 1.2
    },
    options: {
      renderActions: {
        findScript: [10, doc => {
          for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
            const display = !!node.type.match(/; *mode=display/)
            const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
            const text = document.createTextNode('')
            node.parentNode.replaceChild(text, node)
            math.start = {node: text, delim: '', n: 0}
            math.end = {node: text, delim: '', n: 0}
            doc.math.push(math)
          }
        }, ''],
        insertScript: [200, () => {
          document.querySelectorAll('mjx-container:not\([display]\)').forEach(node => {
            const target = node.parentNode
            if (target.nodeName.toLowerCase() === 'li') {
              target.parentNode.classList.add('has-jax')
            } else {
              target.classList.add('has-jax')
            }
          });
        }, '', false]
      }
    }
  }
  
  const script = document.createElement('script')
  script.src = 'https://cdn.jsdelivr.net/npm/mathjax/es5/tex-mml-chtml.min.js'
  script.id = 'MathJax-script'
  script.async = true
  document.head.appendChild(script)
} else {
  MathJax.startup.document.state(0)
  MathJax.texReset()
  MathJax.typeset()
}</script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/katex/dist/katex.min.css"><script src="https://cdn.jsdelivr.net/npm/katex/dist/contrib/copy-tex.min.js"></script><script>(() => {
  document.querySelectorAll('#article-container span.katex-display').forEach(item => {
    btf.wrap(item, 'div', { class: 'katex-wrap'})
  })
})()</script></div><div class="aplayer no-destroy" data-id="7475464662" data-server="netease" data-type="playlist" data-fixed="true" data-mini="true" data-listFolded="false" data-order="random" data-preload="none" data-autoplay="false" muted></div><canvas class="fireworks" mobile="false"></canvas><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/fireworks.min.js"></script><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/metingjs/dist/Meting.min.js"></script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.min.js"></script><script>let pjaxSelectors = ["head > title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"]

var pjax = new Pjax({
  elements: 'a:not([target="_blank"])',
  selectors: pjaxSelectors,
  cacheBust: false,
  analytics: false,
  scrollRestoration: false
})

document.addEventListener('pjax:send', function () {

  // removeEventListener scroll 
  window.tocScrollFn && window.removeEventListener('scroll', window.tocScrollFn)
  window.scrollCollect && window.removeEventListener('scroll', scrollCollect)

  typeof preloader === 'object' && preloader.initLoading()
  document.getElementById('rightside').style.cssText = "opacity: ''; transform: ''"
  
  if (window.aplayers) {
    for (let i = 0; i < window.aplayers.length; i++) {
      if (!window.aplayers[i].options.fixed) {
        window.aplayers[i].destroy()
      }
    }
  }

  typeof typed === 'object' && typed.destroy()

  //reset readmode
  const $bodyClassList = document.body.classList
  $bodyClassList.contains('read-mode') && $bodyClassList.remove('read-mode')

  typeof disqusjs === 'object' && disqusjs.destroy()
})

document.addEventListener('pjax:complete', function () {
  window.refreshFn()

  document.querySelectorAll('script[data-pjax]').forEach(item => {
    const newScript = document.createElement('script')
    const content = item.text || item.textContent || item.innerHTML || ""
    Array.from(item.attributes).forEach(attr => newScript.setAttribute(attr.name, attr.value))
    newScript.appendChild(document.createTextNode(content))
    item.parentNode.replaceChild(newScript, item)
  })

  GLOBAL_CONFIG.islazyload && window.lazyLoadInstance.update()

  typeof chatBtnFn === 'function' && chatBtnFn()
  typeof panguInit === 'function' && panguInit()

  // google analytics
  typeof gtag === 'function' && gtag('config', '', {'page_path': window.location.pathname});

  // baidu analytics
  typeof _hmt === 'object' && _hmt.push(['_trackPageview',window.location.pathname]);

  typeof loadMeting === 'function' && document.getElementsByClassName('aplayer').length && loadMeting()

  // prismjs
  typeof Prism === 'object' && Prism.highlightAll()

  typeof preloader === 'object' && preloader.endLoading()
})

document.addEventListener('pjax:error', (e) => {
  if (e.request.status === 404) {
    pjax.loadUrl('/404.html')
  }
})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>